\section{Problema 2}

\subsection{Introducci\'on}	   

En este ejercicio se debe calcular la región del jardín que está a salvo de las langostas. Las langostas saltan una altura fija y en el jardín hay una serie de vallas donde cada una tiene su propia altura y longitud (es importante notar que las vallas sólo pueden tener dos direcciones: oeste-este ``|'' o sur-norte ``$\mid$''). El objetivo es encontrar y calcular las áreas del jardín encerradas, tal que las langostas no puedan alcanzar, debido a que la altura de las vallas es mayor o igual a la capacidad de salto de las langostas. 

\subsection{Desarrollo}

A priori, el jardín no tiene un tamaño definido. Podemos asumir que el tamaño del jardín es definido por la disposición de las vallas. De esta manera, podemos definir un rectángulo que encuadre a todas las vallas involucradas en el problema. 

Asimismo, para resolver el problema, en vez de calcular el área cubierta, vamos a hallar el área que no está protegida y restarla al área total del rectángulo-jardín. El tamaño del jardín estará determinado por el mayor extremo norte de las vallas verticales y el mayor extremo este de las vallas horizontales.

Asumimos que las coordenadas en que se encuentran las vallas son naturales sin incluir al 0. Es decir, que no hay vallas en los límites del jardín.

Una vez que tenemos las vallas, descartamos aquellas que tienen altura menor a la que llegan las langostas. Como sólo nos interesan las áreas que están encerradas por vallas con altura mayor, las de menor altura no nos interesan y las podemos descartar.

Con el filtro de vallas realizado, dividimos el jardín como una cuadrícula de rectángulos. Para definir estos rectángulos, se realizan proyecciones de líneas horizontales y verticales en el jardín. Las proyecciones de las líneas verticales, provienen de la extensión de las vallas verticales, y las proyecciones verticales de los puntos extremos de las vallas horizontales. Igualmente, las proyecciones horizontales se definen de la extensión de las vallas horizontales, junto con la proyecciones horizontales de los extremos de las vallas verticales.  Para dividirlo, primero llenamos de puntos el jardín, donde una coordenada cualquiera tendrá un punto si y sólo si en esa coordenada termina o empieza una valla o se cruzan/tocan dos vallas. Con todos los puntos identificados, establecemos una recta vertical y una horizontal para cada punto, para formarnos la cuadrícula. El invariante de cada rectángulo es que se conecta con a lo sumo 4 rectángulos y que ninguna valla se cruza por medio de un rectángulo (sólo puede pasar por el borde). Además, los rectángulos se pueden dividir en dos subconjuntos disjuntos tales que representan exactamente al área protegida y al área desprotegida respectivamente.

Una vez obtenida la representación del jardín, por medio de esta ``matriz cuadriculada'' compuesta de rectángulos, se procede a calcular el área ``desprotegida'' o ``descubierta'' del jardín. La idea es modelarlo con un grafo, pensando en los rectángulos descubiertos como nodos del grafo, y dos nodos se relacionan entre sí, si y solo si son adyacentes y se comunican sin una valla tal que los separe. Es decir, sabemos que vamos recorriendo todos los nodos (rectángulos), tal que son propensos a ser invadidos por las langostas. De esta manera, sabemos que con un algoritmo de recorrido de nodos (BFS o DFS), se puede recorrer toda el área desprotegida e ir calculando ese valor, sumando las áreas de todos los rectángulos involucrados. Se decidió que, en vez de usar BFS o DFS, se puede realizar un recorrido similar en forma recursiva, tal que intente inundar los rectángulos adyacentes a uno dado, en orden Norte, Este, Oeste, Sur.

Lo siguiente es armar el grafo. Allí los nodos son los rectángulos e, inicialmente, están relacionados con otros rectángulos tales que estén pegados. \color{black}Luego, partiendo desde el primer rectángulo (el que se encuentra en el extremo inferior izquierdo), que está infectado por la asunción de que no pueden haber vallas en los límites, vamos a ir \textit{inundando} los nodos adyacentes bajo la premisa de: 
\begin{compactitem}
\item Si el siguiente nodo adyacente ya esta inundado, no hacemos nada.
\item Si hay una valla entre ambos nodos, entonces no se puede inundar. \color {red} 
\color{black}
\item Si no está inundado y no hay una valla entre ellos, inundo el nuevo nodo (es decir, acumulamos su área en el total acumulado y hacemos que empiece a inundar a sus adyacentes recursivamente).
\end{compactitem}

Por último, para obtener la solución, restamos al tamaño total del jardín, el área total calculada que está desprotegida.


\newpage

\subsection{Pseudoc\'odigo}
En el archivo \textit{Problem2.java} podremos encontrar la función principal y sus auxiliares. Y a su vez, en los archivos  \textit{Rectangle.java}, \textit{Valla.java}, \textit{HorizontalHardlesComparator.java} y \textit{VerticalHardlesComparator.java} se encuentran las clases auxiliares.

\underline{Estructura:}
\begin{compactitem}
	\item \textbf{LocustsJumpHeight:} Altura que saltan las langostas.
	\item \textbf{Hurdles:} Lista con todas las vallas.
	\item \textbf{ExposedArea:} Acumulador encargado de guardar las áreas expuestas.
	\item \textbf{Garden:} El jardín es un rectángulo delimitado por las vallas horizontales y verticales mas lejanas.
	\item \textbf{GardenMatrix:} Representación del jardín como una matriz de subrectángulos.
	\item \textbf{Horizontal/VerticalHurdles:} Listas con las vallas horizontales y verticales.
	\item \textbf{Horizontal/VerticalProjections:} Listas con las proyecciones horizontales y verticales de las vallas.
\end{compactitem}

\begin{parr}
\begin{algorithm}[H]
\caption{\operMA{Problem2}{ \vin{locustsHeight}{int}, \vin{hurdles}{lista de Vallas}}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \COMMENT{Obtenemos los datos de la instancia.}
\STATE this.locustsJumpHeight $\leftarrow$ locustsHeight
\STATE this.hurdles $\leftarrow$ hurdles
\STATE
\STATE \COMMENT{Eliminamos aquellas vallas tales que por su altura, no podrán cubrir los saltos de las langostas.}
\STATE		filterUselessHurdles(hurdles)
\STATE
\STATE \COMMENT{Separamos las vallas entre horizontales y verticales.}
\STATE		divideHurdles(hurdles)
\STATE \COMMENT{Me devuelve las vallas separadas en horizontal/verticalHurdles}
\STATE
\STATE \COMMENT{Se ordenan las vallas horizontales y verticales.}
\STATE ordenar horizontalHurdles de mayor a menor
\STATE ordenar verticalHurdles de mayor a menor
%\STATE		Collections.sort(horizontalHurdles, horizontalHurdlesComparator)
%\STATE		Collections.sort(verticalHurdles, verticalHurdlesComparator)
\STATE
\STATE \COMMENT{Creamos el jardín como un rectángulo. El punto origen (0,0) es la arista inferior izquierda del jardín.}
\STATE \COMMENT{Se extiende en 1 las dimensiones del jardín, a partir de las últimas vallas horizontales y verticales.}
\STATE		\textbf{var} lastIndex $\leftarrow$ verticalHurdles.size() - 1
\STATE		\textbf{var} xLimit $\leftarrow$ verticalHurdles.get(lastIndex).getX() + 1

\STATE		lastIndex $\leftarrow$ horizontalHurdles.size() - 1
\STATE		\textbf{var} yLimit $\leftarrow$ horizontalHurdles.get(lastIndex).getY() + 1

\STATE		garden $\leftarrow$ Rectangle(0, xLimit, 0, yLimit)
\STATE
\STATE \COMMENT{Para poder definir la matriz de rectángulos, necesitamos tener las proyecciones verticales y horizontales de las vallas y los puntos extremos.}
\STATE		calculateProjections()
\STATE
\STATE \COMMENT{Creación de la matriz de rectángulos.}
\STATE		createRectanglesGarden()
\STATE
\STATE \COMMENT{Cálculo del área expuesta del jardín.}
\STATE \COMMENT{Se empieza por el rectángulo ubicado en la posición (0,0) de la matriz.}
\STATE		calculateExposedArea(0, 0)
\STATE
\STATE \COMMENT{Están todos los cálculos hechos. Sólo resta hacer getCoveredArea() para obtener el área protegida.}

\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Línea 1-2: Inicialización de variable y copia de vallas. $ O(vallas) $.
	\item Línea 6: $ O(vallas) $, recorro las vallas y elimino en $ O(1) $ a las que correspondan.
	\item Línea 9: $ O(vallas) $, recorro las vallas y las voy separando (agregando en $ O(1) $ en otras 2 listas paralelas.
	\item Línea 13-14: $ O(vallas * log(vallas)) $: es el costo de ordenar los horizontales y verticales.
	\item Línea 18-22: $ O(1) $, inicialización y asignación de variables y creación de un rectángulo (constante).
	\item Línea 25: $ O(vallas * log(vallas)) $ (explicación luego)
	\item Línea 28: $ O(vallas^{2}) $ (explicación luego)
	\item Línea 32: $ O(vallas^{3}) $ (explicación luego)
	\item \textbf{\underline{Tiempo Final:}} $ O(vallas+vallas+vallas+vallas*log(vallas)+vallas*log(vallas)+vallas^{2}+vallas^{3}) = O(vallas^{3}) $
\end{compactitem}
\end{algorithm}

La función \textit{calculateExposedArea} calcula el área expuesta, a merced de las langostas.
\begin{algorithm}[H]
\caption{\operMA{calculateExposedArea}{ \vin{x}{int}, \vin{y}{int}}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \COMMENT{Si el rectangulo no fue recorrido, marcarlo y acumular su area.}
\IF{gardenMatrix[x][y] no está marcado }
	\STATE marcar gardenMatrix[x][y]
	\STATE exposedArea $\leftarrow$ exposedArea + área de gardenMatrix[x][y]
\ENDIF

\STATE \COMMENT{Intentar inundar los rectángulos adyacentes.}
\STATE		moveAdjacentRectangles(x, y)
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Línea 2-5: A la matriz y a los datos que ésta contiene, se accede en tiempo constante.
	\item Línea 7: La llamada recursiva se va a repetir en cada uno de los rectángulos (que se encuentran en $O(vallas^{2})$. En cada uno de esos llamados pregunta para cada uno de sus 4 posibles rectángulos adyacentes si hay una valla que los separa, lo que se hace recorriendo todas las vallas $(O(vallas))$. Luego tenemos $O(vallas^{2})$ iteraciones donde en cada una se recorre O(vallas). $O(vallas^{2} * vallas) = O(vallas^{3})$.
	\item \underline{\textbf{Tiempo Final:}} $O(vallas^{3})$
\end{compactitem}
\end{algorithm}

%La función \textit{moveAdjacentRectangles} intenta invadir a los rectángulos adyacentes.
%\begin{algorithm}[H]
%\caption{\operL{moveAdjacentRectangles}{ \vin{x}{int}, \vin{y}{int}}}
%\begin{algorithmic}[1]\parskip=1mm
%\STATE \COMMENT{isValidRectangle indica si el rectángulo está dentro de los límites del jardín.}
%\STATE \COMMENT{canInvade chequea si no hay vallas de por medio.}
%\STATE \COMMENT{Si es válido y puede invadir, llama recursivamente a}
%\STATE \COMMENT{la función calculateExposedArea para que siga invadiendo.}
%\IF{isValidRectangle(x + 1, y) \&\& canInvade(x, y, x + 1, y)}
%	\STATE calculateExposedArea(x + 1, y)
%\ENDIF
%\STATE \COMMENT{Se repite para los 4 puntos cardinales}
%
%	
%\end{algorithmic}
%Complejidades:
%\begin{compactitem}
%	\item Línea 6: 
%	\item Línea 7:
%\end{compactitem}
%\end{algorithm}

%La función \textit{canInvade} chequea si las langostas pueden moverse de un rectángulo al otro.
%\begin{algorithm}[H]
%\caption{\operL{canInvade}{ \vin{x}{int}, \vin{y}{int}, \vin{newX}{int}, \vin{newY}{int}}}
%\begin{algorithmic}[1]\parskip=1mm
%%%%   Esta se podria sacar tambien
%\STATE \COMMENT{Dependiendo de qué valores recibe como entrada,}
%\STATE \COMMENT{determina dónde debería estar la valla que separa los rectángulos.}
%\IF{x $>$ newX}
%	\STATE \COMMENT{Significa que estoy viendo el límite oeste}
%	\STATE			return jumpAllowed(gardenMatrix[x][y].getBeginX(), 
%	\STATE		~~~~~~~~~~~ gardenMatrix[x][y].getBeginY(), 
%	\STATE		~~~~~~~~~~~ gardenMatrix[x][y].getEndY(), '$\mid$')
%	%\STATE		\ELSIF{x $<$ newX}
%	%\STATE			return jumpAllowed(gardenMatrix[x][y].getEndX(),
%	%\STATE					gardenMatrix[x][y].getBeginY(),
%	%\STATE					gardenMatrix[x][y].getEndY(), '|');
%	%\STATE		\ELSIF {y $>$ newY}
%	%\STATE			return jumpAllowed(gardenMatrix[x][y].getBeginY(),
%	%\STATE			gardenMatrix[x][y].getBeginX(),
%	%\STATE					gardenMatrix[x][y].getEndX(), '-');	
%	%\STATE		\ELSE
%	%\STATE			return jumpAllowed(gardenMatrix[x][y].getEndY(),
%	%\STATE					gardenMatrix[x][y].getBeginX(),
%	%\STATE					gardenMatrix[x][y].getEndX(), '-');
%\ENDIF
%\STATE \COMMENT {Se repite para los 4 posibles lados.}
%
%	
%\end{algorithmic}
%Complejidades:
%\begin{compactitem}
%	\item Línea 4: Comparación en tiempo constante.
%	\item Línea 6: Función jumpAllowed $\rightarrow$
%\end{compactitem}
%\end{algorithm}

La función \textit{moveAdjacentRectangles} llama recursivamente a la función \textit{calculateExposedArea} para los 4 rectángulos adyacentes (en caso de existir y que puedan ser inundados, lo cual se determina con \textit{jumpAllowed}).
\begin{algorithm}[H]
\caption{\operL{jumpAllowed}{ \vin{offset}{int}, \vin{segmentBegin}{int}, \vin{segmentEnd}{int}, \vin{direction}{char}}{boolean}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \textbf{var} canJump $\leftarrow$ true
\STATE \textbf{var} hurdles $\leftarrow$ Lista de Vallas
\STATE \COMMENT{Dependiendo de \textit{direction}, determino si necesito revisar las vallas verticales u horizontales.}
%\STATE \COMMENT{determino si necesito revisar las vallas verticales u horizontales.}
\IF{direction == '$\mid$'}
	\STATE			hurdles $\leftarrow$ verticalHurdles
\ELSE
	\STATE			hurdles $\leftarrow$ horizontalHurdles
\ENDIF
\STATE \COMMENT{En \textit{hurdles} voy a tener la lista con las vallas que voy a chequear.}
\FOR{i \textbf{from} 0 \textbf{to} tamaño de hurdles}
	\STATE \COMMENT{Para cada una de las vallas, me fijo si alguna me bloquea para saltar.}
	\STATE \COMMENT{Es decir, recorro las vallas y me fijo si alguna se encuentra en la línea offset y entre segmentBegin y segmentEnd}
	\IF{isolatesRectangles(offset, segmentBegin, segmentEnd, hurdles.get(i)} 
		\STATE				\textbf{return} false
	\ENDIF
\ENDFOR
\STATE \COMMENT{Si ninguna valla me bloqueó, puedo pasar.}
\STATE		\textbf{return} canJump

\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Línea 1-2: Inicialización int y lista vacia, $O(1)$.
	\item Línea 4-8: Comparación $ O(1) $, copia de vallas $ O(vallas) $.
	\item Línea 10-16: $ O(vallas) $ iteraciones donde para cada valla, comparo si el límite del rectángulo se encuentra dentro del de la respectiva valla en tiempo constante. Luego tengo $ O(vallas) $
	\item \textbf{\underline{Tiempo Final:}} $ O(vallas) $
\end{compactitem}
\end{algorithm}

%\begin{algorithm}[H]
%\caption{\operL{isolatesRectangles}{ \vin{offset}{int}, \vin{segmentBegin}{int}, \vin{segmentEnd}{int}, \vin{hurdle}{Valla}}{boolean}}
%\begin{algorithmic}[1]\parskip=1mm
%%%		Esta se podria sacar
%\STATE \COMMENT{Chequeo si la valla está dentro de los límites del segmento.}
%\STATE	\textbf{var} isolatesRectangles $\leftarrow$ false
%\IF {hurdle.getD() == '$\mid$'}
%	\STATE \COMMENT{Primero veo que la valla esté en el mismo eje que el segmento.}
%	\IF {hurdle.getX() == offset}
%		\STATE isolatesRectangles $\leftarrow$ segmentBegin $>$= hurdle.getY() \&\& segmentEnd $<$= hurdle.getY() + hurdle.getW()
%	\ENDIF
%\ELSE 
%	\IF {hurdle.getY() == offset}
%		\STATE isolatesRectangles $\leftarrow$ segmentBegin $>$= hurdle.getX() \&\& segmentEnd $<$= hurdle.getX() + hurdle.getW()
%	\ENDIF
%\ENDIF
%\STATE \textbf{return} isolatesRectangles;
%\end{algorithmic}
%Complejidades:
%\begin{compactitem}
%	\item Línea 6: 
%	\item Línea 7:
%\end{compactitem}
%\end{algorithm}

\begin{algorithm}[H]
\caption{\operMA{createRectanglesGarden}{}}
\begin{algorithmic}[1]\parskip=1mm
% No se si tiene mucho sentido esta tampoco
\STATE \COMMENT {Creo el jardín. Es decir, una matriz de rectángulos.}
\STATE gardenMatrix $\leftarrow$ crear matriz de tamaño de horizontalProjections + 1 por tamaño de verticalProjections + 1
%\STATE gardenMatrix $\leftarrow$ Rectangle[verticalProjections.size() + 1][horizontalProjections.size() + 1]
\STATE \textbf{var} horizontalBegin $\leftarrow$ 0
\STATE \textbf{var} verticalBegin $\leftarrow$ 0
%\FOR {i \textbf{from} 0 \textbf{to} horizontalProjections.size() + 1}
%	\FOR {j \textbf{from} 0 \textbf{to} verticalProjections.size() + 1}
\FOR {i \textbf{from} 0 \textbf{to} tamaño de horizontalProjections + 1}
	\FOR {j \textbf{from} 0 \textbf{to} tamaño de verticalProjections + 1}
		\IF{j == tamaño de verticalProjections}
			\IF{i == tamaño de horizontalProjections}
				\STATE gardenMatrix[i][j] $\leftarrow$ crear rectángulo con horizontalBegin, obtener pos j-1 de verticalProjections + 1, verticalBegin, obtener pos i-1 dehorizontalProjections + 1
			\ELSE 
				\STATE gardenMatrix[i][j] $\leftarrow$ crear rectángulo con horizontalBegin, obtener pos j-1 de verticalProjections + 1, verticalBegin, obtener pos i de horizontalProjections
			\ENDIF
		\ELSE
			\IF{i == tamaño de horizontalProjections}
				\STATE gardenMatrix[i][j] $\leftarrow$ crear rectángulo con horizontalBegin, obtener pos j de verticalProjections, verticalBegin, obtener pos i-1 de horizontalProjections.get(i - 1) + 1)
			\ELSE
				\STATE gardenMatrix[i][j] $\leftarrow$ crear rectángulo con horizontalBegin, obtener pos j de verticalProjections, verticalBegin, obtener pos i de horizontalProjections
			\ENDIF
			\STATE horizontalBegin $\leftarrow$ obtener pos j de verticalProjections
		\ENDIF
	\ENDFOR
	\STATE horizontalBegin $\leftarrow$ 0
	\IF {i $<$ tamaño de horizontalProjections}
		\STATE verticalBegin $\leftarrow$ obtener pos i de horizontalProjections
	\ENDIF
\ENDFOR
	
%		\STATE gardenMatrix[i][j] $\leftarrow$ Rectangle(	horizontalBegin, 
%															verticalProjections.get(j), 
%															verticalBegin,
%															horizontalProjections.get(i))
%		\STATE verticalBegin $\leftarrow$ verticalProjections.get(j)
%	\ENDFOR
%	\STATE horizontalBegin $\leftarrow$ horizontalProjections.get(i + 1)
%\ENDFOR
\end{algorithmic}
Complejidades:
\begin{compactitem}
%	\item Línea 1: Crear el rectángulo implica simplemente poner como atributos del mismo esos parámetros.  $ O(1) $
	\item Línea 2: Crea una matriz de tamaño \textit{verticalProjections} $*$ \textit{horizontalProjections}. Ambos están en $ O(vallas) $ (explicación en \textbf{2.5}). Luego la matriz cuesta $ O(vallas^{2}) $.
	\item Línea 3-4: Inicialización de variables. $ O(1) $.
	\item Línea 5-21: Recorro la matriz entera, $ O(vallas^{2}) $, y en cada iteración creo un rectángulo (lo implica simplemente poner como atributos del mismo los valores pasados como parámetro), $ O(1) $.
	\item \textbf{\underline{Tiempo Final:}} $ O(vallas^{2}) $.
\end{compactitem}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operMA{calculateProjections}{}}
\begin{algorithmic}[1]\parskip=1mm
%esto se podría hacer para uno solo y nombrar que es igual para el otro
\STATE \textbf{var} verticalProjections, horizontalProjections $\leftarrow$ Lista de Enteros
\STATE \COMMENT {Obtenemos los extremos de las vallas horizontales.}
\FOR {i \textbf{from} 0 \textbf{to} tamaño de horizontalHurdles}
	\STATE \textbf{var} hurdle $\leftarrow$ obtener pos i de horizontalHurdles
	\STATE agregar coord X de hurdle a verticalProjections
	\STATE agregar coord X + longitud de hurdle a verticalProjections
\ENDFOR
\STATE \COMMENT{Obtenemos los extremos de las vallas verticales.}
\FOR {i \textbf{from} 0 \textbf{to} tamaño de verticalHurdles}
	\STATE \textbf{var} hurdle $\leftarrow$ obtener pos i verticalHurdles
	\STATE agregar coord Y de hurdle a horizontalProjections
	\STATE agregar coord Y + longitud de hurdle a  horizontalProjections
\ENDFOR
\STATE \COMMENT{Obtenemos las proyecciones de las vallas verticales.}
\FOR {i \textbf{from} 0 \textbf{to} tamaño de  verticalHurdles}
	\STATE agregar coord Y de la pos i de verticalHurdles a verticalProjections
\ENDFOR
\STATE \COMMENT{Obtenemos las proyecciones de las vallas horizontales.}
\FOR {i \textbf{from} 0 \textbf{to} tamaño de horizontalHurdles}
	\STATE agregar coord X de la pos i de horizontalHurdles a horizontalProjections
\ENDFOR
\STATE \COMMENT{Ordenamos las proyecciones}
\STATE ordenar de mayor a menor horizontalProjections
\STATE ordenar de mayor a menor verticalProjections
		
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Línea 1:  Lista vacía, $ O(1) $.
	\item Línea 3-13: Recorro las vallas horizontales/verticales, $ O(vallas) $. En cada iteración creo y copio una valla, $ O(1) $, y agrego 2 elementos a la respectiva lista de vallas, $ O(1) $. Como todo lo hago por duplicado, tengo $ O(2*vallas) = O(vallas) $.
	\item Línea 15-21: Recorro las vallas horizontales/verticales, $ O(vallas) $. En cada iteración, agrego un elemento (el eje en que se encuentra) en tiempo constante. Como todo lo hago por duplicado, tengo $ O(2*vallas) = O(vallas) $.
	\item Línea 23-24: Ordenar una lista de tamaño $ \mid vallas \mid $ toma $ O(vallas * log(vallas)) $ 
	\item \textbf{\underline{Tiempo Final:}} $ O(vallas * log(vallas) + vallas + vallas) = O(vallas * log(vallas)) $
\end{compactitem}
\end{algorithm}%\footnote{http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html\#sort\%28java.util.List\%29}


%\begin{algorithm}[H]
%\caption{\operL{divideHurdles}{\vin{hurdles}{Lista de Vallas}}}
%\begin{algorithmic}[1]\parskip=1mm
%\STATE \textbf{var} horizontalHurdles, verticalHurdles $\leftarrow$ Lista de Vallas
%\STATE \textbf{var} hurdlesIterator $\leftarrow$ hurdles.iterator()
%\WHILE {hurdlesIterator.hasNext()}
%	\STATE \textbf{var} hurdle $\leftarrow$ hurdlesIterator.next()
%	\IF {hurdle.getD() == '$\mid$'}
%		\STATE verticalHurdles.add(hurdle)
%	\ELSE 
%		\STATE horizontalHurdles.add(hurdle);
%	\ENDIF
%\ENDWHILE		
%\end{algorithmic}
%Complejidades:
%\begin{compactitem}
%	\item Línea 6: 
%	\item Línea 7:
%\end{compactitem}
%\end{algorithm}

%\begin{algorithm}[H]
%\caption{\operL{filterUselessHurdles}{\vin{hurdles}{Lista de Vallas}}}
%\begin{algorithmic}[1]\parskip=1mm
%\STATE \textbf{var} hurdlesIterator $\leftarrow$ hurdles.iterator()
%\WHILE {hurdlesIterator.hasNext()}
%	\STATE \textbf{var} hurdle $\leftarrow$ hurdlesIterator.next()
%	\STATE \COMMENT{Si la altura de la valla es menor a la capacidad de salto de las langostas, entonces se elimina la valla.}
%	\IF {hurdle.getH() < locustsJumpHeight}
%		\STATE hurdles.remove(hurdle)
%	\ENDIF
%\ENDWHILE		
%\end{algorithmic}
%Complejidades:
%\begin{compactitem}
%	\item Línea 6: 
%	\item Línea 7:
%\end{compactitem}
%\end{algorithm}

%La función \textit{getCoveredArea} me devuelve el resultado final, cuánto espacio está protegido de las langostas.
%\begin{algorithm}[H]
%\caption{\operL{getCoveredArea}{}{int}}
%\begin{algorithmic}[1]\parskip=1mm
%\STATE \textbf{return} getGardenArea() - exposedArea;
%\STATE \COMMENT {\textit{getGardenArea} me devuelve el área total del jardín.}
%\STATE \COMMENT {En \textit{exposedArea} tengo el área total desprotegida.}
%\end{algorithmic}
%Complejidades:
%\begin{compactitem}
%	\item Línea 6: 
%	\item Línea 7:
%\end{compactitem}
%\end{algorithm}




\end{parr}
\newpage
\subsection{Demostración de la solución}
% Tendría que demostrar: el invariante de los rectángulos, o sea, que no pasan vallas por el medio, sólo por los bordes, y que los rectángulos se pueden dividir en dos subconjuntos disjuntos tales que uno forma exactamente el área protegida y el otro forma exactamente el área desprotegida.
% También que se recorren todos los rectángulos no protegidos (al final, no queda ningún rectángulo desprotegido sin recorrer)
\subsubsection{Demostración Invariante Rectángulos}
%\begin{center}
%    \begin{tabular}{ | p{17cm} |}
%	\hline 	\\ 
%	 Entonces, el procedimiento sería el siguiente:
%	\begin{compactenum}
%		\item Aplicar una función biyectiva a los investigadores para identificarlos uno con uno con un vértice en el grafo. La vuelta también es posible de así requerirlo (de vértice en el grafo a nombre de investigador).
%		\item Generar el grafo con sus vértices y ejes de tal manera que se pueda buscar en tiempo constante los vértices adyacentes a un vértice dado. Si dos investigadores son amigos sus respectivos vértices son adyacentes en el grafo y viceversa.
%		\item Aplicar el algoritmo de BFS-modificado al grafo generado.
%		\item Devolver la solución
%	\end{compactenum}
%	\\ \hline
%    \end{tabular}
%\end{center}
Debemos probar dos cosas: que las vallas no se cruzan por el medio de los rectángulos (solamente se pueden tocar en los bordes) y que los rectángulos se pueden dividir en dos subconjuntos disjuntos tales que uno forma exactamente el área protegida y el otro forma exactamente el área desprotegida.

Para lo primero, hay que ver cómo se generan los rectángulos. Las \textit{proyecciones} tanto verticales están determinadas por los extremos de las vallas horizontales y por los ejes de las vallas verticales (el caso horizontal es análogo). Por cada proyección pasa una línea horizontal y otra vertical formando la grilla. Luego, supongamos que hay un rectángulo que contiene una valla dentro de él. Pero como mencionamos antes, esa valla genera proyecciones las cuales generan líneas en la grilla que dividirían el rectángulo en 2. Esto es un absurdo ya que nosotros vemos los rectángulos mínimos, y ése contiene a otros dos.

%Para lo segundo, podemos usar lo anteriormente probado. Sabemos que no hay rectángulos que contengan vallas y también sabemos que el jardín está completamente ocupado por rectángulos. Además, sabemos que un área está protegida si está rodeada de vallas y esas vallas me generan las proyecciones para los rectángulos que están dentro de esta.

%Una forma de probar eso es ver que un rectángulo no puede estar al mismo tiempo en un área protegida y un área desprotegida. 

Para lo segundo, podemos usar lo anteriormente probado. Sabemos que no hay rectángulos que contengan vallas y también sabemos que el jardín está completamente ocupado por rectángulos. Un rectángulo está protegido si todos los rectángulos adyacentes están protegidos o separados por una valla. A su vez, un rectángulo está desprotegido si alguno de todos los rectángulos adyacentes está desprotegido y no hay una valla que los separa. Como son opuestos, no pueden suceder ambos al mismo tiempo. Luego probamos que los dos subconjuntos son disjuntos.
%Para ver que cada subconjunto representa efectivamente al área respectiva, supongamos que hay un rectángulo desprotegido dentro de un área protegida. Como dijimos antes, para que esto pase tiene que estar rodeado por al menos un rectángulo desprotegido 

Por otro lado, para desde un rectángulo desprotegido cualquiera poder infectar a otro rectángulo adyacente, no tiene que haber una valla entre ellos. Pero por definición de área protegida, ésta esta encerrada por vallas. Eso significa que nunca voy a poder infectar un rectángulo protegido.

\subsubsection{Demostración Correctitud Recorrido}
%Por un lado, cuando creamos el jardín dejamos un borde externo desprotegido para poder ``ingresar'' por cualquier hueco que haya entre vallas. Luego, para probar que nosotros al recorrer pasamos por todos los rectángulos desprotegidos

Para probar que al recorrer el jardín pasamos por todos los rectángulos desprotegidos (y por cada uno, se pasa una sola vez) supongamos que hay un rectángulo $ R $ desprotegido que no fue accedido. Antes que nada, recordemos que cuando creamos el jardín dejamos un borde externo desprotegido para poder ``ingresar'' por cualquier hueco que haya entre vallas. Para que ese rectángulo $ R $ sea efectivamente desprotegido, tiene que tener algún rectángulo adyacente desprotegido y sin una valla que los separe. Pero en nuestro algoritmo, cuando se para en un rectángulo desprotegido, llama recursivamente para los adyacentes tales que no hay un valla que los separe. Luego, si no \textit{invadió} significa que había una valla separándoles. \textbf{Absurdo:} si hay una valla separando a $ R $ de sus adyacentes desprotegidos entonces es falsa nuestra suposición de que $ R $ es desprotegido. Si no fue accedido, es porque está protegido.

\subsection{Complejidad (modelo uniforme)}
La complejidad del algoritmo es $ O(vallas^{3}) $ que resulta, como se puede ver en el pseudocódigo, de aplicar el constructor (que a su vez llama a diferentes funciones auxiliares) y obtener el resultado en $ O(1) $ con \textit{getCoveredArea}. La función que marca la diferencia es \textit{calculateExposedArea}, quien recorre todos los rectángulos del jardín, $ O(vallas^{2}) $, y para cada una recorre todas las vallas, $ O(vallas) $, para ver a cuáles de los 4 rectángulos adyacentes avanza.

Las otras funciones se encuentran por debajo de la complejidad cúbica, por ejemplo, en \textit{createRectanglesGarden} recorremos la matriz del jardín, $ O(vallas^{2}) $; en \textit{calculateProjections} recorremos las vallas y ordenamos, lo que nos deja en $ O(vallas * log(vallas)) $; entre otros.

En cuanto a la cantidad de rectángulos, ésta está acotada por $ \mid vallas \mid^{2} $ ya que la cantidad de filas y columnas en peor caso, está determinada por la cantidad de proyecciones de las vallas. Las vallas verticales generan 2 proyecciones horizontales y 1 vertical y las horizontales lo opuesto. Luego, cada valla me genera a lo sumo 2 proyecciones verticales y 2 proyecciones horizontales. Si tenemos $ 2~ * \mid vallas \mid $ filas y $ 2~ * \mid vallas \mid $ columnas, vamos a tener a la cantidad de rectángulos acotada por $ 4~ * \mid vallas \mid^{2} $.

\newpage

\subsection{Tests}
Para realizar las mediciones de los tests, se usa una variable-contador insertada en el código, la cual va contando cada una de las operaciones básicas que se realizan a lo largo de algoritmo.
\subsubsection{Análisis de peores casos}
Para realizar el test de rendimiento y poder verificar la complejidad calculada, debemos considerar los peores casos para nuestro algoritmo. En este caso, cualquier jardín el cual tenga una cantidad $n$ de vallas dispuestas, pero que no formen áreas protegidas de las langostas, será un buen jardín para considerar como mal caso para nuestro algoritmo. Esto se debe a que el algoritmo tendrá prácticamente toda el área del jardín descubierta para recorrer y calcular. Si hubiera una gran área del jardín cubierta, esto representaría menos área descubierta para recorrer por el algoritmo.



\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej2/peorcaso.pdf,width=0.9\linewidth,clip=}
\caption{Tests para peores casos.}
\end{figure}



Podemos ver como los puntos correspondientes a las mediciones inducen una curva muy similar a la curva cúbica ($n^3$), verificando empíricamente la complejidad temporal calculada.\\

\newpage

\color{black}
\subsubsection{Análisis de mejores casos}
Para considerar los mejores casos, se debe pensar en instancias cuya zona cubierta sea lo mas amplia posible, y cuya zona descubierta sea la menor posible. De esta manera, el recorrido realizado por el algoritmo es el menor posible, minimizando la cantidad de operaciones y de llamadas recursivas.\\
Se generaron instancias, las cuales tienen un ``anillo exterior'' como zona descubierta, y en el centro un rectángulo como zona cubierta.



\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej2/mejorcaso.pdf,width=0.9\linewidth,clip=}
\caption{Tests para mejores casos.}
\end{figure}



En este caso consideramos que nada más está desprotegido el ``anillo exterior''. Luego cuando nosotros recorremos, empezando por el primer rectángulo todas las áreas desprotegidas, nada más estamos recorriendo el anillo exterior. Luego como cada ``fila'' y cada ``columna'' tiene un tamaño acotado del orden de la cantidad de vallas, vamos a recorrer $ 4~* \mid vallas \mid $ rectángulos. Para cada uno de estos rectángulos, debemos intentar invadir a los adyacentes, que nos cuesta recorrer todas las vallas buscando una que los separe. Finalmente tenemos $ O(vallas) $ iteraciones donde en cada iteración cuesta $ O(vallas) $ lo que nos en tiempo final $ O(vallas^{2}) $ (recordar que las otras funciones, como ya vimos, se encuentran por debajo del costo cuadrático por lo que las podemos ignorar).



\color{black}

\subsubsection{Caso especial}
\color{black}Para evaluar la correctitud del funcionamiento del algoritmo, se realizaron varias pruebas. Estas pruebas se realizaron sobre instancias generadas arbitrariamente, intentando encontrar fallas en el algoritmo. A continuación se presenta y describe un caso interesante, para mostrar esto. Se consideró en especial generar una instancia lo suficientemente complicada, como para poder verificar fehacientemente que el algoritmo recorre correctamente las áreas descubiertas del jardín.\\

Se decidió crear una instancia, tal que el área cubierta tiene la forma de una espiral encerrada, cuyo interior no puede ser accedido por las langostas. De esta manera, se espera que el algoritmo pueda acceder a las regiones descubiertas tal que por su forma, tambien se convierten en espiraladas. Dicha instancia se encuentra en el archivo de entrada \textit{Ej2Espiral.in}. Las dimensiones totales del jardín son de $12 x 10$, con un área total de $120$, y un área descubierta de $86$. Eso nos deja que el área encerrada por la espiral es exactamente $34$. Al ejecutar el algoritmo con esta instancia, dicho resultado correcto es devuelto al archivo de salida \textit{Ej2Espiral.out}.\\
 
\color{black} 
\subsection{Conclusiones}
Nos resultó dificultoso pensar la idea para poder resolver este problema. Una vez encontrado el método, resulta intuitivo y simple pensar el cálculo del área cubierta como el cálculo del área complemento (desprotegida), particionando el jardín en regiones rectangulares disjuntas.